#pragma once

namespace Ut
{

uint32 Hash(uint32 i)
{
	return (uint32) std::hash<uint32>()(i);
}

template <typename Key, typename Value>
class HashTable
{
public:
	HashTable(int n) 
	{
		Rebuild(n);
	}

	void Rebuild(int n)
	{
		std::vector<Element> data;
		data.resize(n);
		std::swap(m_data, data);
		Clear();

		for (auto& element : data)
		{
			if (element.present)
			{
				Insert(element.entry.key, element.entry.value);
			}
		}
	}

	int Size() const
	{
		return m_size;
	}

	void Insert(const Key& key, const Value& value)
	{
		(*this)[key] = value;
	}

	Value Lookup(const Key& key, const Value& defaultValue) const
	{
		if (m_data.empty())
			return defaultValue;

		uint32 hash = Hash(key);
		int i = hash % m_data.size();

		while (m_data[i].present == true)
		{
			if (m_data[i].entry.key == key)
				return m_data[i].entry.value;

			if (++i == (int) m_data.size()) i = 0;
		};

		return defaultValue;
	}

	Value& operator [] (const Key& key)
	{
		if (m_size + m_size / 2 > (int) m_data.size())
			Rebuild((int) m_data.size() + (int) m_data.size() / 2);

		uint32 hash = Hash(key);
		int i = hash % m_data.size();

		while (m_data[i].present == true)
		{
			if (m_data[i].entry.key == key)
				return m_data[i].entry.value;

			if (++i == (int) m_data.size()) i = 0;
		};

		m_size++;
		m_data[i].present = true;
		m_data[i].entry.key = key;
		return m_data[i].entry.value;
	}

	void Clear()
	{
		m_size = 0;

		for (auto& entry : m_data)
			entry.present = false;
	}

private:
	template <typename Key, typename Value> friend void Swap(HashTable& a, HashTable& b);

	struct Entry
	{
		Key key;
		Value value;
	};

	struct Element
	{
		bool present;
		Entry entry;
	};

	std::vector<Element> m_data;
	int m_size;
};

template <typename Key, typename Value>
void Swap(HashTable<Key, Value>& a, HashTable<Key, Value>& b)
{
	std::swap(a.m_data, b.m_data);
	std::swap(a.m_size, b.m_size);
}

}